1. Field of the Invention
The present invention relates to a Viterbi decoder and a Viterbi decoding method, and more specifically, to a Viterbi decoder and a Viterbi decoding method in a register exchange method.
2. Description of the Related Art
Various digital communication standards adopt a convolutional encoding method to perform forward error correction (FEC). An information bit sequence encoded in the convolutional encoding method is decoded by a Viterbi decoder in a receiver.
FIG. 1 shows a diagram of a configuration of a convolutional encoder having a constraint length K of 7 according to the IEEE802.16 international standard.
As shown in FIG. 1, the convolutional encoder having the constraint length K of 7 according to the IEEE802.16 international standard includes two XOR operators 11 and 12, and six delay units 21 to 26. The convolutional encoder receives one bit among the information bit sequence for every clock signal through a first delay unit 21, and generates two encoded symbols with the two XOR operators 11 and 12. The convolutional code is classified as a zero-tail convolutional code and a tail-biting convolutional code.
The zero-tail convolutional encoding method will now be described with reference to FIG. 2 to FIG. 4.
FIG. 2 shows a diagram for representing a unit packet of encoded bits of an encoder in the zero-tail convolutional encoding method.
As shown in FIG. 2, the unit packet of encoded bits of the encoder in the zero-tail convolutional encoding method is formed by adding a sequence of (K−1) zero-bits (a zero-tail sequence) to the information bit sequence. Therefore, when L denotes the size of the information bit sequence, the size of unit packet of encoded bits of the encoder in the zero-tail convolutional encoding method is L+K−1. When the constraint length K is 7, the unit packet of encoded bits includes L+6 bits.
FIG. 3 shows a diagram for representing an initial state of the encoder in the zero-tail convolutional encoding method. As shown in FIG. 3, each delay unit has a value of 0 when the encoder in the zero-tail convolutional encoding method is at the initial state. Therefore, a Viterbi decoder in the zero-tail convolutional encoding method may start a decoding operation from the 0 state.
FIG. 4 shows a diagram for representing an end state of the encoder in the zero-tail convolutional encoding method. As shown in FIG. 4, the end state of the encoder in the zero-tail convolutional encoding method is the 0 state in which each delay unit has the value of 0. Since 0 values of the last K−1 bits of the unit packet are inputted to the convolutional encoder, the end state of the encoder in the zero-tail convolutional encoding method becomes the 0 state. Therefore, the Viterbi decoder in the zero-tail convolutional encoding method may start a trace-back operation from the 0 state.
Since the additional zero tail sequence having the values of 0 is used in the zero-tail convolutional encoding method, an error may be easily corrected when the last part of the information bit sequence has the error. In addition, the Viterbi decoder may start the decoding and trace-back operations from the 0 state since both the initial and end states of the convolutional encoder are 0, and therefore a configuration of the Viterbi decoder may be simplified. However, there is a problem in that the data rate is reduced due to the additional zero tail sequence in the zero-tail convolutional encoding method. To solve the problem, the tail-biting convolutional encoding method has been suggested.
The tail-biting convolutional encoding method will now be described with reference to FIG. 5 to FIG. 7.
FIG. 5 shows a diagram for representing a unit packet of encoded bits of an encoder in the tail-biting convolutional encoding method. As shown in FIG. 5, the unit packet of encoded bits of the encoder in the tail-biting convolutional encoding method has no additional data. Therefore, the data rate in the tail-biting convolutional encoding method is better than that in the zero-tail convolutional encoding method.
FIG. 6 shows a diagram for representing an initial state of the encoder in the tail-biting convolutional encoding method. As shown in FIG. 6, the initial state of the encoder in the tail-biting convolutional encoding method is determined by the last 6 bits of the unit packet. Since the last 6 bits of the unit packet of the encoder in the tail-biting convolutional encoding method are not 0, the initial state of the encoder in the tail-biting convolutional encoding method is not 0. The encoder in the tail-biting convolutional encoding method preferentially receives the last 6 bits of the unit packet before performing an encoding operation, so as to establish the initial state of the encoder as the last 6 bits of the decoding unit packet. At this time, the encoder in the tail-biting convolutional encoding method does not generate an encoded output bit. Then, the encoder in the tail-biting convolutional encoding method sequentially receives the information bit sequence, and generates the encoded output bit.
FIG. 7 shows a diagram for representing the end state of the encoder in the tail-biting convolutional encoding method. As shown in FIG. 7, differing from the zero-tail convolutional encoding method, the end state in the tail-biting convolutional encoding method is determined by the last 6 bits of the information bit sequence since the end state includes no additional zero-bit. Therefore, the initial and end states of the encoder in the tail-biting convolutional encoding method are the same.
In addition, the initial and end states of the encoder in the tail-biting convolutional encoding method are not 0 since those are determined by the last 6 bits of the unit packet. Therefore, the Viterbi decoder in the tail-biting convolutional encoding method has a problem in determining the initial state, and therefore the configuration of the Viterbi decoder is problematically complicated.
A method for obtaining a final decoding bit sequence by the Viterbi decoder classified as a trace-back method and a register exchange method.
The Viterbi decoder using the trace-back method performs a forward decoding process and a trace-back process. In the forward decoding process, the Viterbi decoder calculates a branch metric BM from the received input bit sequence (i.e., the branch metric corresponding to each branch on a trellis), calculates a path metric PM from the branch metric (i.e., the path metric corresponding to a path to a next state), and selects a survival path by using the calculated path metric. In the trace-back process, the Viterbi decoder traces back the selected survival path to extract a final decoding bit sequence. The Viterbi decoding method according to the trace-back method will be described with reference to FIG. 8.
FIG. 8 shows a diagram exemplifying a trellis according to the convolutional encoding method.
As shown in FIG. 8, the Viterbi decoder selects a survival path 31 by using a path metric, and extracts a final decoding bit sequence by tracing back the selected survival path 31. In this case, the path metric is not continuously increased since the path metric is normalized.
The Viterbi decoder in the register exchange method has registers at respective states. The Viterbi decoder in the register exchange method performs branch metric and path metric operations to select a path, and adds new path selection information to a register in a previous state of the selected path so as to update the register corresponding to respective current states. Since the register at each state stores a decoded bit sequence corresponding to a path reaching each state, the Viterbi decoder decodes the unit packet of encoded bits and outputs a bit sequence included in a register at an optimum state as the final decode bit sequence. The optimum state indicates a state having a minimum path metric. The Viterbi decoding method according to the register exchange method will be described with reference to FIG. 9.
FIG. 9 shows a diagram exemplifying a register exchange Viterbi decoding process on the trellis.
As shown in FIG. 9, the Viterbi decoder in the register exchange method includes registers corresponding to respective states. In addition, the Viterbi decoder in the register exchange method adds a piece of decode information to the registers at the respective states as a decode operation proceeds, and the registers at the respective states are exchanged with each other according to the survival path.
In the Viterbi decoding method according to the register exchange method, there is a merit in that a time for performing a decoding operation is reduced compared to the trace-back method since it is not required to perform the trace-back operation. Specifically, when the Viterbi decoder in the zero-tail convolutional encoding method uses the trace-back method, the time for performing the decoding operation may be reduced by half compared to the trace-back method. The Viterbi decoder using the tail-biting convolutional encoding method needs an operation for determining an initial state of the decoding operation since the Viterbi decoder may not be informed of the initial state of the decoding operation, but when the Viterbi decoder uses the register exchange method, the time for performing the decoding operation may be reduced compared to the trace-back method.
However, in the register exchange method, since decoding performance generally depends on a forward decoding operation, a bit error rate (BER) is deteriorated compared to the trace-back method. When a bit error occurs on a former part of the information bit sequence by a channel distortion, decoding reliability is reduced. Specifically, since the Viterbi decoder in the tail-biting convolutional encoding method may not correctly determine the initial state, the decoding reliability is further reduced.
In addition, the Viterbi decoder in the register exchange method includes registers at respective states, respective values of the registers frequently vary according to the selected path, and therefore the power consumption may be increased. Further, since the size of the register is increased according to the length of the unit packet of encoded bits, the power consumption is further increased as the length of the unit packet is increased.
A modified register exchange method has been developed to solve the above problem. In the modified register exchange method, the values stored in the respective registers are not exchanged, but pointers corresponding to state values are exchanged to exchange the registers. Since the Viterbi decoder in the modified register exchange method exchanges relatively fewer bits, the power consumption may be reduced. When the constraint length K is 7, the number of register value transitions is given as Equation 1, as follows:{64(state)*1(bit)+64(state)*6(bit)}=448 times  (1)
When the constraint length K is 7, the number of states is 64, and therefore the number of register value transitions is 64. In addition, an address of the pointer is 6 bits, and therefore the number of register value transitions caused by the exchange of the pointers is 64*6.
However, in the published modified register exchange method, a considerable number of unit registers are required when the length of the unit packet is increased, since an increase of the length of the unit packet is not considered. For example, when the constraint length is 7 and the length of the unit packet is 480 bits, a required unit register may be given as 480*64=30,720 bits, which is difficult to realize in an integrated circuit.
Other problems of the modified register exchange method will be described with reference to FIG. 10.
FIG. 10 shows a diagram representing the conventional modified register exchange method.
As shown in FIG. 10, in the Viterbi decoder in the modified register exchange method, a value of a register selected for two paths is copied in another register which is not used. In this case, the register which is not used has a different value from a value that was to be originally copied to the register, and therefore, the number of transitions of the register values may be increased, which increases the power consumption. For example, since the register 21 is selected for two paths, the value of the register 21 is copied and stored in the register 23 that is excluded to select the path and is eliminated. The register 23 has the value which is different from the value which was to be copied in the register 23. Therefore, the number of register transitions of the modified register exchange method is increased as shown in Equation 2, as follows:{(Info_len*D)+64(state)*1(bit)+64(state)*6(bit)}>>448 times  (2)
As shown in Equation 2, a number obtained by multiplying the length Info_len of the unit packet by a frequency D is required to be added to the number of register transitions of the modified register exchange method. The frequency D is the number of cases that one register is selected for two paths. For example, when the length of the unit packet is 480 bits and D=10, the number of register transitions is increased by 4,800 times, which is a great number compared to 488 times.
The above information disclosed in this Background section is only for enhancement of understanding of the background of the invention and therefore it may contain information that does not form the prior art that is already known in this country to a person of ordinary skill in the art.